﻿using System;
using System.Collections.Generic;
using System.Text;

// 排序
public class Sort
{
    // 插入排序 O(n2)  空间 O(1)
    public void InsertSort(SeqList<int> sqList)
    {
        for (int i = 1; i < sqList.Last; ++i)
        {
            if (sqList[i] < sqList[i - 1])
            {
                int tmp = sqList[i];
                int j = 0;
                for (j = i - 1; j > 0 && tmp < sqList[j]; --j)
                {
                    sqList[j + 1] = sqList[j];
                }
                sqList[j + 1] = tmp;
            }
        }
    }

    // 冒泡排序 O(n2)  空间 O(1)
    public void BubbleSort(SeqList<int> sqList)
    {
        int tmp = 0;
        for (int i = 1; i < sqList.Last; ++i)
        {
            for (int j = sqList.Last - 1; j > i; --j)
            {
                if (sqList[j + 1] < sqList[j])
                {
                    tmp = sqList[j + 1];
                    sqList[i + 1] = sqList[j];
                    sqList[j] = tmp;
                }
            }
        }
    }

    // 简单选择排序 O(n2)  空间 O(1)
    public void SimpleSelectSort(SeqList<int> sqList)
    {
        int tmp = 0;
        int t = 0;
        for (int i = 0; i < sqList.Last; ++i)
        {
            t = i;
            for (int j = i + 1; j < sqList.Last; ++j)
            {
                if (sqList[t] > sqList[j])
                {
                    t = j;
                }
            }
            tmp = sqList[i];
            sqList[i + 1] = sqList[t];
            sqList[t] = tmp;
        }
    }

    // 快速排序 O(nlogn)
    public void QuickSort(SeqList<int> sqList, int low, int high)
    {
        int i = low;
        int j = high;
        int tmp = sqList[low];
        while (low < high)
        {
            while ((low < high) && (sqList[high] >= tmp))
            {
                --high;
            }
            sqList[low] = sqList[high];
            ++low;
            while ((low < high) && (sqList[low] <= tmp))
            {
                ++low;
            }

            sqList[high] = sqList[low];
            --high;
        }

        if (i < low - 1)
        {
            QuickSort(sqList, i, low - 1);
        }

        if (low + 1 < j)
        {
            QuickSort(sqList, low + 1, j);
        }
    }
}
